package leecode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author wangxi created on 2021/3/29 23:01
 * @version v1.0
 * https://leetcode-cn.com/problems/merge-intervals/
 */
public class MergeIntervals {
    public static void main(String[] args) {
        int[][] internals = {{1,3}, {2,6},{8,10},{15,18}};
        MergeIntervals obj = new MergeIntervals();
        int[][] merge = obj.merge(internals);
        for (int[] item : merge) {
            System.out.println(Arrays.toString(item));
        }
    }

    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals[0] == null) {
            return new int[0][0];
        }
        Arrays.sort(intervals, (num1, num2) -> {
            return num1[0] - num2[0];
        });

        List<int[]> list = new ArrayList<>();
        // 提前初始化一个元素，写起来会顺畅很多
        list.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] pre = list.get(list.size() - 1);
            int[] cur = intervals[i];
            if (pre[1] < cur[0]) {
                list.add(cur);
            } else {
                pre[1] = Math.max(pre[1], cur[1]);
            }
        }
        int[][] res = new int[list.size()][2];
        int i = 0;
        for (int[] item : list) {
            res[i++] = item;
        }
        return res;
    }
}
